The Purpose of Topological Sort - Educational Content

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) that respects all dependencies defined by the edges.

The primary goal is to find a linear ordering of all vertices in a DAG.
The fundamental rule is that for every directed edge $u \to v$, vertex $u$ must appear before vertex $v$ in the final sequence.
This ordering represents a valid sequence of tasks where prerequisites must be completed first (e.g., compiling code, scheduling jobs).
A DAG can often have multiple valid topological sorts, depending on the relative order of independent nodes.
If a graph contains a cycle, a topological sort is impossible, as the dependency rule cannot be satisfied.

Formal Definition: Topological Sort

An ordering of vertices $(v_1, v_2, \dots, v_n)$ in a DAG $G=(V, E)$ such that if $(v_i, v_j)$ is an edge in $E$, then the index $i$ must be less than the index $j$.

Requirement: Graph must be a DAG.